home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / N_TREE.H < prev    next >
C/C++ Source or Header  |  1992-09-28  |  10KB  |  245 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 07/06/89 -- Initial design
  13. // Updated: MBN 08/15/89 -- Inherit from Generic and initial implementation
  14. // Updated: MBN 09/19/89 -- Added conditional exception handling
  15. // Updated: MBN 02/27/90 -- Added constructor that takes a pointer to node and
  16. //                          the current_depth() member function
  17. // Updated: MJF 03/12/90 -- Added group names to RAISE
  18. // Updated: VDN 02/21/92 -- New lite version
  19. // Updated: JAM 08/19/92 -- modernized template syntax, remove macro hacks
  20. // Updated: JAM 08/19/92 -- made *_state typedef a nested typedef "IterState"
  21. //                          as per new Iterator convention
  22. // Updated: JAM 09/28/92 -- made Node class have ItemType and nchild members
  23. //                          so don't have to give template parameters twice
  24. //
  25. // The  N_Tree  class  implements  N-ary  trees,  providing  the organizational
  26. // structure for a tree  (collection) of nodes,  but  knowing nothing about the
  27. // specific type of node  used. N_Tree is parameterized  over a node type and a
  28. // data type, where the node specified  must have a data slot  of the same type
  29. // Type as the N_Tree  class. Two node classes are  provided, but others  could
  30. // also be written.  The  N_Node class implements  static-sized nodes for  some
  31. // particular "N" number of sub-trees, and the D_Node class  implements dymamic
  32. // sized nodes derived from the Vector class.
  33. //
  34. // Since the organization of a tree is important (as  with an expression tree),
  35. // the user must supervise the construction  of  the tree by directing specific
  36. // node and sub-tree assignment and layout.   No attempt  is made by the N_Tree
  37. // class to balance or prune the tree.
  38. //
  39. // The N_Tree class supports the concept  of a  current  position and a current
  40. // traversal mode. When  the traversal  mode  is  set, the current position  is
  41. // invalidated.  The  first call   to advance the   current position causes  an
  42. // internal dynamic cache of pointers to nodes to  be created ordered according
  43. // to the traversal mode. Future current position  methods then act  based upon
  44. // the information in  the cache.   Any method that  changes the tree structure
  45. // invalidates the cache.
  46. //
  47. // There are two  public constructors. The  first takes a  reference  to a Node
  48. // object and constructs an N_Tree object whose root is the supplied node.  The
  49. // second takes a reference  to an existing  N_Tree  object and duplicates  its
  50. // size and contents.  The N_Tree class has four private data slots.  The first
  51. // contains a pointer to the root of the tree, the second maintains the current
  52. // position,  the  third contains a pointer to  a  dynamic cache of pointers to
  53. // nodes used  by  the current  position  methods, and  the   fourth contains a
  54. // pointer to the default node comparison function.  In addition, there are two
  55. // private methods.  The first is used to create the cache of pointers to nodes
  56. // upon the first dispatch to  advance the current position,  and the second is
  57. // the default node comparison function to be used  if the user  does not chose
  58. // to provide one.
  59. //
  60. // All methods  in the  N_Tree class  support  the organization, structure, and
  61. // traversal of a tree.  Methods to allow manipulation  of individual nodes and
  62. // sub-trees is located in the node classes. N_Tree has methods to search for a
  63. // sub-tree,  find a  node with a specific value,  and return a  pointer to the
  64. // parent of the current  node. The reset, next, prev,  value, remove, and find
  65. // methods provide a mechanism to  iterate  through the nodes  of a tree  based
  66. // upon  the current position. The specific  traversal mechanism  for  use with
  67. // this iteration can be set with  the set_traversal method,  and all nodes can
  68. // be removed  from the tree   with  clear.  Finally,  methods  are provided to
  69. // traverse the  tree in  either preorder, inorder,  or  postorder and apply  a
  70. // user-specified function to each node.
  71. //
  72.  
  73. #ifndef N_TREEH                    // If no definition for class
  74. #define N_TREEH
  75.  
  76. #ifndef N_TREE_STATEH
  77. #include <cool/NT_State.h>            // Include NT_State
  78. #endif
  79.  
  80. #ifndef BASE_BINARY_TREEH
  81. enum Left_Right {NONE, LEFT, RIGHT};
  82. enum Traversal_Type {PREORDER, INORDER, POSTORDER,
  83.              PREORDER_REVERSE, INORDER_REVERSE, POSTORDER_REVERSE};
  84. #endif
  85.  
  86.  
  87. template <class Node>
  88. class CoolN_Tree {
  89. public:
  90.   typedef CoolNT_State IterState;
  91.   typedef Boolean (*Apply_Function)(const Node::ItemType&);
  92.  
  93.   CoolN_Tree(Node* root=NULL); // Default
  94.   CoolN_Tree(Node& root); // Simple constructor
  95.   CoolN_Tree(const CoolN_Tree<Node>&);    // Copy
  96.   ~CoolN_Tree();        // Destructor
  97.  
  98.   void clear ();                // Empty the tree
  99.   inline long count ();                // Return number of nodes
  100.   inline void reset ();                // Current position invalid
  101.   inline Traversal_Type& traversal ();        // Set/Get the traversal mode
  102.   inline Node*& operator[] (int); // Set/Get pointers
  103.  
  104.   inline Boolean next ();            // Advance to next node
  105.   Boolean prev ();                    // Backup to previous node
  106.   Node::ItemType& value (){/*##;*/            // Get value at current position
  107. #if ERROR_CHECKING 
  108.       if (this->state.stack.is_empty() )        // If no position established
  109.          this->value_error ();            // Raise exception
  110. #endif
  111.       CoolNT_Stack_Entry stack_entry = this->state.stack.top();
  112.       return (((Node*)stack_entry.get_first())->get());
  113.       }
  114.   Boolean find (const Node::ItemType& value){/*##;*/            // Search for item in tree
  115.       for (this->reset (); this->next (); )     // For each node in tree
  116.          if (this->value() == value)            // If node found in tree
  117.             return TRUE;                // Inidicate success
  118.       return FALSE;                    // Inidicate failure
  119.       }
  120.   inline CoolNT_State& current_position();        // Get/Set Tree's curpos
  121.   inline long current_depth () const;        // Depth of curpos in tree
  122.  
  123.   void preorder (Apply_Function fn){/*##;*/    // Preorder traversal
  124.       if (this->t_mode != PREORDER)         // If incorrect traversal mode
  125.          this->t_mode = PREORDER;            // Set preorder mode
  126.       for (this->reset() ; this->next (); )        // For each preorder node
  127.          (*fn)(this->value());            // Apply function
  128.       }
  129.   void inorder (Apply_Function fn){/*##;*/        // Inorder traversal
  130.       if (this->t_mode != INORDER)          // If incorrect traversal mode
  131.          this->t_mode = INORDER;            // Set inorder mode
  132.       for (this->reset() ; this->next (); )        // For each preorder node
  133.          (*fn)(this->value());            // Apply function
  134.       }
  135.   void postorder (Apply_Function fn){/*##;*/    // Postorder traversal
  136.       if (this->t_mode != POSTORDER)         // If incorrect traversal mode
  137.          this->t_mode = POSTORDER;            // Set postorder mode
  138.  
  139.       for (this->reset() ; this->next (); )        // For each preorder node
  140.          (*fn)(this->value());            // Apply function
  141.       }
  142.  
  143.   CoolN_Tree<Node>& operator= (const CoolN_Tree<Node>&);
  144.   inline operator Node*() const; // Conversion to node ptr
  145.  
  146. private:
  147.   Node* root;        // Root of tree
  148.   long number_nodes;                // Number of nodes in tree
  149.   Traversal_Type t_mode;            // Retains traversal type
  150.   CoolNT_State state;                // Iterator state for CoolN_Tree
  151.  
  152.   void do_count (Node*);        // Count nodes in tree
  153.   Boolean next_internal (Traversal_Type);    // Moves current_position
  154.   inline Node* copy_nodes(const Node*) const; // Copy subnodes
  155.  
  156.   void value_error ();                // Raise exception
  157. };
  158.  
  159. // Reset -- Initialize current position of Tree
  160. // Input:   None
  161. // Output:  None
  162.  
  163. template <class Node> 
  164. inline void CoolN_Tree<Node>::reset () {
  165.   this->state.stack.clear();
  166. }
  167.  
  168.  
  169. // count -- Return number of nodes in tree
  170. // Input:   None
  171. // Output:  Number of nodes in tree
  172.  
  173. template <class Node> 
  174. inline long CoolN_Tree<Node>::count () {
  175.   this->number_nodes = 0;            // Initialize count
  176.   this->do_count (this->root);            // Count nodes in tree
  177.   return this->number_nodes;            // Return node count
  178. }
  179.  
  180.  
  181. // set_traversal -- Set traversal mode
  182. // Input:           Traversal type
  183. // Output:          None
  184.  
  185. template <class Node> 
  186. inline Traversal_Type& CoolN_Tree<Node>::traversal () {
  187.   return (this->t_mode);            // Traversal mode
  188. }
  189.  
  190.  
  191. // operator[] -- Overload the brackets operator to provide a mechanism to set
  192. //               and/or get a sub-tree pointer of a node whose zero-relative
  193. //               index is specified from left to right
  194. // Input:        Zero-relative index into vector of sub-tree pointers
  195. // Output:       Reference to a pointer value
  196.  
  197. template <class Node> 
  198. inline Node*& CoolN_Tree<Node>::operator[] (int index) {
  199.   return (this->root->sub_trees[index]);
  200. }
  201.  
  202.  
  203. // next -- Move current position to next node in tree. If no more nodes
  204. //         return FALSE
  205. // Input:  None
  206. // Output: TRUE/FALSE
  207.  
  208. template <class Node> 
  209. inline Boolean CoolN_Tree<Node>::next () {
  210.   return next_internal (this->t_mode);
  211. }
  212.  
  213.  
  214.  
  215. // current_depth -- Get current depth of current position in tree
  216. // Input:           None
  217. // Output:          Depth of current position node in tree
  218.  
  219. template <class Node>
  220. inline long CoolN_Tree<Node>::current_depth () const {
  221.   return this->state.stack.length() - 1;
  222. }
  223.  
  224.  
  225. // operator Node -- Provide an accessor to the encapsulated Node object
  226. // Input:           None
  227. // Output:          Pointer to node object
  228.  
  229. template <class Node> 
  230. inline CoolN_Tree<Node>::operator Node* () const
  231. {
  232.   return this->root;
  233. }
  234.  
  235.  
  236. template <class Node>
  237. inline Node* CoolN_Tree<Node>::copy_nodes(const Node* n) const{
  238.   Node* new_nodes = NULL;
  239.   if (n)
  240.     new_nodes = n->copy_nodes(n);        // recursive deep copy
  241.   return new_nodes;
  242. }
  243.  
  244. #endif                        // End N_TREEH #if
  245.